/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 009. 乘积小于 K 的子数组
 * @author: WXY
 * @create: 2022-12-21 14:08
 * @Version 1.0
 **/

public class offer_three3_numSubarrayProductLessThanK {
    public static int numSubarrayProductLessThanK(int[] arr, int k) {
        int left = 0;
        int right = 0;
        int sum = 1;
        int ans = 0;
        while (right < arr.length) {
            sum *= arr[right];
            while (left <= right && sum >= k) {
                sum /= arr[left];
                left++;
            }
            ans += right - left  + 1;
            right++;
        }
        return ans;
    }

    //自己的低效解法
    /*
     public static int numSubarrayProductLessThanK(int[] arr, int k) {
        int left = 0;
        int right = 0;
        int sum = 1;
        int ans = 0;
        while (right < arr.length) {
            sum *= arr[right];
            while (sum < k ) {
                ans++;
                right++;
                if (right == arr.length)break;
                sum *= arr[right];
            }
            left++;
            right = left;
            sum = 1;
        }
        return ans;
    }
     */

    public static void main(String[] args) {
        int[] arr = new int[]{5,2,6};
        int k = 0;
        int num = numSubarrayProductLessThanK(arr, k);
        System.out.println(num);

    }
}
